package com.jerry.hm.datastructure.priorityqueue;

import com.jerry.hm.datastructure.queue.Queue;

/**
 * 基于大顶堆实现的优先级队列
 *
 * @author Jerry
 * @since 2024/10/5 18:12
 */
public class PriorityQueue3<E extends Priority> implements Queue<E> {

    private Priority[] array;
    private int size;

    public PriorityQueue3(int capacity) {
        array = new Priority[capacity];
    }

    /**
     * 向堆添加新元素，要满足大顶堆的特性
     * 不断比较待添加元素和它父节点的优先级。如果父节点优先级低，则父节点下移，并继续向上找父节点。知道父节点优先级更高或者找到根节点位置。
     *
     * @param e
     * @return
     */
    @Override
    public boolean offer(E e) {
        if (isFull()) {
            return false;
        }

        int child = size++;
        int parent = (child - 1) / 2;
        while (child > 0 && e.priority() > array[parent].priority()) {
            array[child] = array[parent];
            child = parent;
            parent = (child - 1) / 2;
        }
        array[child] = e;
        return true;
    }

    /**
     * 从队首移除元素，交换根节点和最后一个元素的位置
     * 让新的根节点和左右两个子节点比较，优先级高的那个和该节点继续交换为止，直到两个子节点的优先级都小于该节点停止。
     *
     * @return
     */
    @Override
    public E poll() {
        if (isEmpty()) {
            return null;
        }

        Priority e = array[0];
        swap(0, --size);
        array[size] = null;

        // 下潜操作
        dive(0);
        return (E) e;
    }

    /**
     * 从队首获取元素
     *
     * @return
     */
    @Override
    public E peek() {
        if (isEmpty()) {
            return null;
        }
        return (E) array[0];
    }

    /**
     * 队列是否空
     *
     * @return
     */
    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    /**
     * 队列是否满
     *
     * @return
     */
    @Override
    public boolean isFull() {
        return size == array.length;
    }

    /**
     * 交换两个节点
     *
     * @param i
     * @param j
     */
    private void swap(int i, int j) {
        Priority temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

    /**
     * 下潜操作
     *
     * @param parent
     */
    private void dive(int parent) {
        int left = 2 * parent + 1;
        int right = left + 1;
        int max = parent;
        if (left < size && array[left].priority() > array[max].priority()) {
            max = left;
        }
        if (right < size && array[right].priority() > array[max].priority()) {
            max = right;
        }

        if (max != parent) {
            swap(max, parent);
            dive(max);
        }
    }

}